package dynamicProgramming.bagQuestion;

public class Bag04 {

//    给出 n 个物品, 以及一个数组, nums[i] 代表第i个物品的大小,
//    保证大小均为正数, 正整数 target 表示背包的大小, 找到能填满背包的方案数。

    public int backPackV(int[] nums, int target) {
        // write your code here

        int[][]dp=new int[nums.length+1][target+1];
        for (int i = 0; i < nums.length; i++) {
            dp[i][0]=1;
        }
        for (int index = 1; index<=nums.length; index++) {
            for (int rest = 1; rest <=target; rest++) {
//                if (nums[index-1]>rest){
//                    dp[index][rest]=dp[index-1][rest];
//                }else {
//                    dp[index][rest]=Math.max(nums[index-1]+dp[index-1][rest-nums[index-1]],dp[index-1][rest]);
//                }
                dp[index][rest]=dp[index-1][rest];
                if (rest>=nums[index-1]){
                     //TODO:2024/1/24  rest-nums[index-1]  这个部分控制使得刚好装满
                    dp[index][rest]+=dp[index-1][rest-nums[index-1]];
                }

//                dp[j] 就是所有的dp[j - coins[i]]（考虑coins[i]的情况）相加。
//
//                所以递推公式：dp[j] += dp[j - coins[i]];
            }
        }
        return  dp[nums.length][target];



    }


}
